//JS and Unity
var allBaseLines = new Array();

var edgePoints=[];
function qhPlotConvexHull(data)			//Draw convex hull in graph
{
    //清空变量防止每次循环的时候把前一次的值push进去
     allBaseLines = new Array();
     edgePoints=[];
    let points=[];
    for(let i=0;i<data.length;i++){
        points.push( [ data[i].lng, data[i].lat ] )
    }
    var ch = getConvexHull(points);	//Get Quick Hull Points
    var eBL = allBaseLines[0];

    function plotIntermediateBL()
    {
        var l = allBaseLines.shift();		//Pop first item
        if (l)	//if item exists and popped
        {

            plotIntermediateBL();
        }
        else
        {
            for (var idx in ch)
            {
                var baseLine = ch[idx];
                edgePoints.push(baseLine)
            }


        }
    }
    plotIntermediateBL();
    let ret=[];
    let result =[];
    for( let i=0; i < edgePoints.length;i++ ) {
        ret.push( edgePoints[i][1])
    }

    for(let i=0; i<ret.length;i++ ) {
        for(let z =0;z<data.length;z++ ) {
            if(data[z].lat == ret[i][1] && data[z].lng == ret[i][0]) {
                result.push(data[z])
            }
        }
    }

    return result;
}

function getConvexHull(points)		//Quick hull Algorithm Simulation (Recursive) - Find Points
{
    //find first baseline
    var maxX, minX;			//All points are greater than 0, so no initialization is needed
    var maxPt, minPt;
    for (var idx in points)		//Find 2 extreme points to devide them
    {
        var pt = points[idx];
        if (pt[0] > maxX || !maxX)
        {
            maxPt = pt;
            maxX = pt[0];
        }
        if (pt[0] < minX || !minX)
        {
            minPt = pt;
            minX = pt[0];
        }
    }
    var ch = [].concat(buildConvexHull([minPt, maxPt], points),
        buildConvexHull([maxPt, minPt], points));	//Create upper and lower points and concate them and store
    return ch;
}

//quickhull for one part
function buildConvexHull(baseLine, points)
{
    allBaseLines.push(baseLine);		//Over rites in global value, but not making any problem, because the data is stored then in function
    var convexHullBaseLines = new Array();
    var t = findMostDistantPointFromBaseLine(baseLine, points);
    if (t.maxPoint.length)
    { // if there is still a point "outside" the base line
        convexHullBaseLines =
            convexHullBaseLines.concat(
                buildConvexHull( [baseLine[0],t.maxPoint], t.newPoints)
            );
        convexHullBaseLines =
            convexHullBaseLines.concat(
                buildConvexHull( [t.maxPoint,baseLine[1]], t.newPoints)
            );
        return convexHullBaseLines;
    }
    else
    {	// if there is no more point "outside" the base line, the current base line is part of the convex hull
        return [baseLine];
    }
}

function findMostDistantPointFromBaseLine(baseLine, points)		//Find the most distant point
{
    var maxD = 0;
    var maxPt = new Array();
    var newPoints = new Array();
    for (var idx in points)
    {
        var pt = points[idx];
        var d = getDistant(pt, baseLine);
        if ( d > 0)
        {
            newPoints.push(pt);
        }
        else
        {
            continue;
        }
        if ( d > maxD )
        {
            maxD = d;
            maxPt = pt;
        }
    }
    return {'maxPoint':maxPt, 'newPoints':newPoints};
}

function getDistant(cpt, bl)	//Find distence of point and line
{
    //return ( (cpt[0]*bl[0][1]+bl[0][0]*bl[1][0]+bl[1][1]*cpt[1]-cpt[1]*bl[0][0]-bl[0][1]*bl[1][0]-bl[1][1]*cpt[0])/Math.sqrt( (bl[0][0]-bl[0][1])*(bl[0][0]-bl[0][1]) + (bl[1][0]-bl[1][1])*(bl[1][0]-bl[1][1]) ) );

    var Vy = bl[1][0] - bl[0][0];
    var Vx = bl[0][1] - bl[1][1];
    return (Vx * (cpt[0] - bl[0][0]) + Vy * (cpt[1] -bl[0][1]));
}




